We have developed algorithms for rapid comparison of protein structure and statistical criteria for significance testing. These will be used to detect ancient evolutionary relationships and to identify the common structural "building blocks" of proteins. We define two proteins to be similar if they have a similar composition with respect to secondary structural elements, if these elements are similarly oriented in space, and if they are topologically connected in the same manner. We detect similar orientation and topology of elements using a simplified vector representation and clique detection algorithm, as suggested by P. Willett and colleagues. The similar substructures identified are then ranked according to the probability that they would occur in comparison of dissimilar proteins; the calculation assumes that element-pair comparisons are independent, and calculates chi-square statistics relative to an empirical distribution of random element-pair scores. This procedure is very rapid, allowing comparison of a protein against the non-redundant structures in the Protein Data Bank in approximately 5 seconds. In control experiments The most significant "hits" correspond invariably to known similarities. The top-scoring element-alignments identified in this way then serve as input to a Monte Carlo residue-alignment procedure, which uses a sampling strategy similar to that developed for protein "threading". Comparison employs a conventional root-mean-square distance metric, and significance of alternative possible alignments is evaluated relative to an empirical distribution derived by random alignment of proteins with similar size and core-element composition. Identification of the most surprising substructure similarity requires roughly 1 minute, and often leads to superposition scores superior to those in the literature. The significance of this work will be in extending the horizon to which evolutionary relationship may be detected, by employing structure comparison in place of sequence comparison alone. The results will be made available to biologists as "structural neighbors" in the "Entrez" browser.